/*!
 Temelia - Sorting algorithms implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/sort.h"
#include <stdlib.h>
#include <string.h>

// Private functions.
// Merge sort.
static void _merge_sort(void *data, int begin, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context);

static void _merge(void *data, int begin, int middle, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context);

// Quick sort.
static void _quick_sort(void *data, int begin, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context);

static int _partition(void *data, int begin, int end, void *key_at(void *data,
		int index), void set_key_at(void *data, int index, void *new_value),
		int compare(void *x, void *y, void *context), void *context);

// Heap sort.
static void _heapify(void *data, int n, void *key_at(void *data, int index),
		void set_key_at(void *data, int index, void *new_value), int compare(
				void *x, void *y, void *context), void *context);

static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
		int index), void set_key_at(void *data, int index, void *new_value),
		int compare(void *x, void *y, void *context), void *context);

// Radix sort.
static int _digit(int x, int y);
static int _power(int x);

int is_sorted(void *data, int size, void *(*key_at)(void *data, int index),
		int (*compare)(void *x, void *y, void *context), void *context)
{
	int i;

	_ASSERT(data, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	for (i = 0; i < size - 1; i++)
		if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
			return 0;
	return 1;
}

void bubble_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	void *aux;
	int ordonat, i;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	do
	{
		ordonat = 0;
		for (i = 0; i < size - 1; i++)
		{
			if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
			{
				aux = key_at(data, i);
				set_key_at(data, i, key_at(data, i + 1));
				set_key_at(data, i + 1, aux);
				ordonat = 1;
			}
		}
	} while (ordonat);
}

void insertion_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int i, j;
	void *key, *aux;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	for (j = 1; j < size; j++)
	{
		key = key_at(data, j);
		i = j - 1;
		while (i >= 0 && compare(key_at(data, i), key, context) > 0)
		{
			aux = key_at(data, i);
			set_key_at(data, i, key_at(data, i + 1));
			set_key_at(data, i + 1, aux);
			i--;
		}
	}
}

void merge_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	_merge_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
}

void quick_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	_quick_sort(data, 0, size - 1, key_at, set_key_at, compare, context);
}

void selection_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int i, j, min;
	void *aux;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	for (i = 0; i < size - 1; i++)
	{
		min = i;
		for (j = i + 1; j < size; j++)
			if (compare(key_at(data, j), key_at(data, min), context) < 0)
				min = j;

		aux = key_at(data, i);
		set_key_at(data, i, key_at(data, min));
		set_key_at(data, min, aux);
	}
}

void shell_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int i, j, increment;
	void *temp;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	increment = size / 2;
	while (increment > 0)
	{
		for (i = increment; i < size; i++)
		{
			j = i;
			temp = key_at(data, i);
			while ((j >= increment) && (compare(key_at(data, j - increment),
					temp, context) > 0))
			{
				set_key_at(data, j, key_at(data, j - increment));
				j -= increment;
			}
			set_key_at(data, j, temp);
		}
		if (increment == 2)
			increment = 1;
		else
			increment = (int) (increment / 2.2);
	}
}

void heap_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int end;
	void *aux;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	_heapify(data, size, key_at, set_key_at, compare, context);
	end = size - 1;

	while (end >= 0)
	{
		if (compare(key_at(data, 0), key_at(data, end), context) > 0)
		{
			aux = key_at(data, 0);
			set_key_at(data, 0, key_at(data, end));
			set_key_at(data, end, aux);
			end--;
		}
		else
			end--;
		_sift_down(data, 0, end, key_at, set_key_at, compare, context);
	}
}

void gnome_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int i, j;
	void *aux;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	i = 1;
	j = 2;
	while (i < size)
	{
		if (compare(key_at(data, i - 1), key_at(data, i), context) < 0)
		{
			i = j;
			j++;
		}
		else
		{
			aux = key_at(data, i - 1);
			set_key_at(data, i - 1, key_at(data, i));
			set_key_at(data, i, aux);
			i--;
			if (i == 0)
				i = 1;
		}
	}
}

void cocktail_sort(void *data, int size, void *(*key_at)(void *data, int index),
		void (*set_key_at)(void *data, int index, void *new_value), int (*compare)(
				void *x, void *y, void *context), void *context)
{
	int buttom, top, i;
	void *aux;
	int ordonat = 1;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	buttom = 0;
	top = size - 1;
	while (ordonat)
	{
		ordonat = 0;
		for (i = buttom; i < top; i++)
		{
			if (compare(key_at(data, i), key_at(data, i + 1), context) > 0)
			{
				aux = key_at(data, i);
				set_key_at(data, i, key_at(data, i + 1));
				set_key_at(data, i + 1, aux);
				ordonat = 1;
			}
		}
		top--;
		for (i = top; i > buttom; i--)
		{
			if (compare(key_at(data, i - 1), key_at(data, i), context) > 0)
			{
				aux = key_at(data, i);
				set_key_at(data, i, key_at(data, i - 1));
				set_key_at(data, i - 1, aux);
				ordonat = 1;
			}
		}
		buttom++;
	}
}

void radix_sort(int *data, int size, int max_digits)
{
	queue_t Q[10];
	int i, j, x, *y, *aux;

	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(max_digits, <, 0, INVALID_INPUT,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	for (i = 0; i < 10; i++)
		Q[i] = queue_new(size);

	for (i = 0; i < max_digits; i++)
	{
		for (j = 0; j < size; j++)
		{
			x = _digit(data[j], i);
			y = (int *) _new(sizeof(int));
			*y = data[j];
			queue_push_back(Q[x], y);
		}
		x = 0;
		for (j = 0; j < 10; j++)
		{
			while (!queue_is_empty(Q[j]))
			{
				aux = (int *) queue_get_front(Q[j]);
				data[x++] = *aux;
				queue_pop_front(Q[j]);
				_delete(aux);
			}
		}
	}

	for (i = 0; i < 10; i++)
		queue_delete(Q[i]);
}

#include <stdio.h>

void number_sort(unsigned int *data, int size, int max_value)
{
	int i;
	int j;
	unsigned int *count;
	unsigned int *aux;

	LOGGER("[number_sort] data %p, size %d, max_value %d\n", data, size,
			max_value);
	_ASSERT(data, ==, NULL, NULL_POINTER,);
	_ASSERT(size, <=, 1, INVALID_INPUT,);

	aux = (unsigned int *) _new(size * sizeof(unsigned int));
	count = (unsigned int *) _new(max_value * sizeof(unsigned int));

	_ASSERT(aux, ==, NULL, NULL_POINTER,);
	_ASSERT(count, ==, NULL, NULL_POINTER,);

	memset(count, 0, max_value * sizeof(unsigned int));

	for (j = 0; j < size; j++)
	{
		if (data[j] >= (unsigned int) max_value || data[j] < 0)
		{
			LOGGER("[numer_sort] invalid input %d\n", data[j]);
			temelia_errno = INVALID_INPUT;
			return;
		}
		count[data[j]]++;
	}

	for (i = 1; i < max_value; i++)
		count[i] += count[i - 1];

	for (j = size - 1; j >= 0; j--)
	{
		aux[count[data[j]] - 1] = data[j];
		count[data[j]]--;
	}

	memcpy(data, aux, size * sizeof(unsigned int));

	_delete(aux);
	_delete(count);
}

static void _merge_sort(void *data, int begin, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context)
{
	int mid;

	if (begin < end)
	{
		mid = (begin + end) / 2;
		_merge_sort(data, begin, mid, key_at, set_key_at, compare, context);
		_merge_sort(data, mid + 1, end, key_at, set_key_at, compare, context);
		_merge(data, begin, mid, end, key_at, set_key_at, compare, context);
	}
}

static void _merge(void *data, int begin, int middle, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context)
{
	int i, j, k;
	void **aux;
	aux = (void **) _new((end - begin + 1) * sizeof(void *));

	i = begin;
	j = middle + 1;
	k = 0;
	while (i <= middle && j <= end)
	{
		if (compare(key_at(data, i), key_at(data, j), context) >= 0)
			aux[k++] = key_at(data, j++);
		else
			aux[k++] = key_at(data, i++);
	}
	while (i <= middle)
		aux[k++] = key_at(data, i++);
	while (j <= end)
		aux[k++] = key_at(data, j++);
	for (i = 0; i < k; i++)
		set_key_at(data, begin + i, aux[i]);
	_delete(aux);
}

static void _quick_sort(void *data, int begin, int end, void *key_at(
		void *data, int index), void set_key_at(void *data, int index,
		void *new_value), int compare(void *x, void *y, void *context),
		void *context)
{
	int middle;
	if (begin < end)
	{
		middle = _partition(data, begin, end, key_at, set_key_at, compare,
				context);
		_quick_sort(data, begin, middle, key_at, set_key_at, compare, context);
		_quick_sort(data, middle + 1, end, key_at, set_key_at, compare, context);
	}
}

static int _partition(void *data, int begin, int end, void *key_at(void *data,
		int index), void set_key_at(void *data, int index, void *new_value),
		int compare(void *x, void *y, void *context), void *context)
{
	int i, j;
	void *pivot, *aux;
	pivot = key_at(data, begin + _rand() % (end - begin));
	i = begin - 1;
	j = end + 1;
	while (1)
	{
		do
		{
			i++;
		} while (i < end && compare(key_at(data, i), pivot, context) < 0);

		do
		{
			j--;
		} while (j > begin && compare(key_at(data, j), pivot, context) > 0);

		if (i >= j)
			return j;

		aux = key_at(data, i);
		set_key_at(data, i, key_at(data, j));
		set_key_at(data, j, aux);
	}
}

static void _heapify(void *data, int n, void *key_at(void *data, int index),
		void set_key_at(void *data, int index, void *new_value), int compare(
				void *x, void *y, void *context), void *context)
{
	int start = n / 2 - 1;
	while (start >= 0)
	{
		_sift_down(data, start, n - 1, key_at, set_key_at, compare, context);
		start--;
	}
}

static void _sift_down(void *data, int begin, int end, void *key_at(void *data,
		int index), void set_key_at(void *data, int index, void *new_value),
		int compare(void *x, void *y, void *context), void *context)
{
	int root, child;
	void *aux;
	root = begin;

	while ((root * 2 + 1) < end)
	{
		child = root * 2 + 1;
		if ((child < end) && (compare(key_at(data, child), key_at(data, child
				+ 1), context) < 0))
			child++;

		if (compare(key_at(data, root), key_at(data, child), context) < 0)
		{
			aux = key_at(data, root);
			set_key_at(data, root, key_at(data, child));
			set_key_at(data, child, aux);
			root = child;
		}

		else
			return;
	}
}

static int _digit(int x, int y)
{
	return (x / _power(y)) % 10;
}

static int _power(int x)
{
	int p, i;
	p = 1;
	for (i = 0; i < x; i++)
		p *= 10;
	return p;
}
